package data.structure.linear.heap;


import data.structure.linear.heap.printer.BinaryTrees;

import java.util.Comparator;

public class Main {

    static void test1() {
        BinaryHeap<Integer> heap = new BinaryHeap<>();
        heap.add(68);
        heap.add(72);
        heap.add(43);
        heap.add(50);
        heap.add(38);
        heap.add(10);
        heap.add(90);
        heap.add(65);
        BinaryTrees.println(heap);
        heap.remove();
        BinaryTrees.println(heap);

        System.out.println(heap.replace(70));
        BinaryTrees.println(heap);
    }

    static void test2() {
        Integer[] data = {88, 44, 53, 41, 16, 6, 70, 18, 85, 98, 81, 23, 36, 43, 37};
        BinaryHeap<Integer> heap = new BinaryHeap<>(data);
        BinaryTrees.println(heap);

        data[0] = 10;
        data[1] = 20;
        BinaryTrees.println(heap);
    }

	// 小顶堆   逻辑是 使用compare方法 返回我认为大的值(小值)给大顶堆
    static void test3() {
        Integer[] data = {88, 44, 53, 41, 16, 6, 70, 18, 85, 98, 81, 23, 36, 43, 37};
        BinaryHeap<Integer> heap = new BinaryHeap<>(data, new Comparator<Integer>() {
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        BinaryTrees.println(heap);
    }

    // topK问题二叉堆解决方案  k为topK的个数
	// 时间复杂度为O(nlogk)
    static void test4() {
		// 创建小顶堆
        BinaryHeap<Integer> heap = new BinaryHeap<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });

        Integer[] data = {88, 44, 53, 41, 16, 6, 70, 18, 85, 98, 81, 23, 36, 43, 37};
		// topK个数
        int k = 3;
        for (int i = 0; i < data.length; i++) {
            Integer element = data[i];
            if (heap.size < k) {
                heap.add(element);
            } else if (heap.get() < element) {
                heap.replace(element);
            }
        }
        BinaryTrees.println(heap);
    }

    public static void main(String[] args) {
//		test1();
//        test2();
//        test3();
        test4();
    }

}
